1. Field of the Invention
The present invention relates generally to cryptographic techniques for the construction of symmetric (shared-key) encryption schemes, and more particularly, to ways to use a block cipher in order to construct a highly efficient encryption scheme that simultaneously provides both message privacy and message authenticity.
2. Related Art
When two parties, a Sender and a Receiver, communicate, the parties often need to protect both the privacy and the authenticity of the transmitted data. Protecting the privacy of the data ensures that unauthorized parties will not understand the content of transmissions. Protecting the authenticity of the data provides assurance to the Receiver that the actual Sender of a message coincides with the claimed Sender of the message (and it thereby provides assurance to the Receiver that the message was not accidentally or intentionally modified in transit). Both goals are often accomplished using symmetric (“shared key”) techniques, wherein the Sender and the Receiver make use of a shared key K. We call “authenticated encryption” the goal of simultaneously achieving both privacy and authenticity using shared-key techniques. In an authenticated-encryption method, the Sender can encrypt a message using a key and a nonce (also called an Initialization Vector, or IV) to yield a ciphertext. The Receiver can decrypt a ciphertext using a key and a nonce to yield either a message or a special symbol, invalid, that indicates to the Receiver that the ciphertext should be regarded as inauthentic.
The most common approach for authenticated encryption uses two different tools: for privacy, a privacy-only encryption scheme, and for authenticity, a message authentication code (MAC). Privacy-only encryption schemes compute a ciphertext from a plaintext, a key, and a nonce. Message authentication codes compute an authentication tag (which is a fixed-length string) from a message and a key. To MAC a message means to computes its authentication tag using a message authentication code.
Many constructions for privacy-only encryption schemes and many constructions for message authentication codes are known in the art. Some are described, for example, in the book of Menezes, van Oorschot and Vanstone, Handbook of Applied Cryptography, published by CRC Press, 1997. Both privacy-only encryption schemes and message authentication codes are commonly based on the use of a block cipher.
By way of further background, a block cipher is a function E that takes a key K and a message block X, the key being a binary string from some set of allowed keys and the message block being a binary string of some fixed length n. The block cipher returns a ciphertext block Y=EK(X), which is also a binary string of length n. The number n is called the block length of the block cipher. It is required that for each key K, the function EK is one-to-one and onto (in other words, it is a bijection on the space of n-bit strings). Since EK is one-to-one and onto, it has a well-defined inverse, denoted EK−1. Well known block ciphers include the algorithm of the Data Encryption Standard (DES), which has a block length of n=64 bits, and the algorithm of the Advanced Encryption Standard (AES), which has a block length of n=128 bits. We shall speak of “applying a block cipher” or “enciphering” to refer to the process of taking an n-bit string X and computing from it a string Y=EK(X) for some understood key K and block cipher E. Similarly, we shall speak of “deciphering” to refer to the process of taking an n-bit string Y and computing from it a string X=EK−1(Y).
The most common approach for privacy-only encryption using an n-bit block cipher E is CBC encryption (cipher block chaining encryption). In the “basic” form of CBC encryption, the message M that we wish to encrypt must be a binary string of length that is a positive multiple of the block length n. The message M is partitioned into n-bit blocks M[1], M[2], . . . , M[m] by taking M[1] as the first n bits of M, taking M[2] as the next n bits of M, and so forth. An n-bit nonce, IV, is selected. Then one encrypts M using the key K and the nonce IV by computing, for each iε[1 . . . m], the ciphertext blockC[i]=EK(C[i−1]⊕M[i])where C[0]=IV. The complete ciphertext is IV together with the ciphertext C=C[1] . . . C[m].
Nonces are used quite generally for shared-key encryption. A nonce is a value used at most once (or almost certainly used at most once) within a given context. Most often, nonces are realized using a counter or random value. For CBC encryption, a random value should be used; for CBC encryption, there are problems with using a counter IV.
The most common approach for making a message authentication code using an n-bit block cipher E is the CBC MAC (cipher block chaining message authentication code). In the “basic” form of the CBC MAC, the message M to be authenticated must be a binary string having a length that is a positive multiple of n. The message M is partitioned into n-bit blocks M[1], M[2], . . . , M[m] by taking M[1] as the first n bits of M, taking M[2] as the next n bits of M, and so forth. One then computes the authentication tag of M, using key K, by way of the same algorithm used for CBC encryption, but where the IV=0, the block of n zero bits, and where the authentication tag is the final ciphertext block, Tag=C[m]. Only Tag, or a prefix of Tag, is output as the authentication tag. A Receiver who obtains an authenticated message M∥Tag checks the validity of M by re-computing the CBC MAC of M under key K, obtaining a string Tag′, and verifying that Tag′ is identical to Tag.
To combine CBC encryption and the CBC MAC, in order to obtain both privacy and authenticity, use the generic composition method. One uses two keys: an encryption key Ke and a message-authentication key Ka. In one method for generic composition, the message M is CBC encrypted using key Ka and nonce IV to yield an intermediate ciphertext Cint=IV∥C[1] . . . C[m]. Then the intermediate ciphertext Cint is MACed using the CBC MAC under key Ka to yield an authentication tag Tag. The ciphertext for the authenticated-encryption scheme is C=C[1] . . . C[m]∥Tag. The Receiver, on receipt of IV and C[1] . . . C[m]∥Tag, checks that Tag is the CBC MAC of Cint=IV∥C[1] . . . C[m] under key Ka. If the received Tag is what the Receiver computes it should be, the Receiver decrypts C[1] . . . C[m] using key Ke and nonce IV to obtain the plaintext M. If the received Tag is different from what the Receiver computes it should be, the Receiver rejects the received ciphertext C=C[1] . . . C[m]∥Tag, regarding it as invalid.
The same generic-composition approach can be used to combine any privacy-only encryption scheme with any message authentication code.
There are a number of limitations to the generic composition approach. The main limitation is that two sequential computing passes are made over the data, one to privacy-only encrypt and one to MAC, making the process twice as slow as privacy-only encryption (assuming that privacy-only encryption and MAC computation take about the same amount of time, as they would for CBC encryption and the CBC MAC). Privacy-only encryption can be computationally expensive, and adding in a major additional expense to ensure message authenticity is considered undesirable in many settings.
Because of the limitation just described, individuals have tried for many years to merge privacy and authenticity into a single, unified process that would be nearly as fast as conventional ways to do privacy-only encryption. Until quite recently, all such attempts failed. For a history of some of the failed attempts, see the survey article of Bart Preneel entitled Cryptographic Primitives for Information Authentication—State of the Art, appearing in State of the Art of Applied Cryptography, COSIAC '97, Lecture Notes in Computer Science, vol. 1528, Springer-Verlag, pp. 49-104, 1998. As an example of a particularly recent attempt, Gligor and Donescu describe an incorrect authenticated-encryption mode in their paper Integrity Aware PCBC Encryption, appearing in Security Protocols, 7th International Workshop, Cambridge, UK, Apr. 19-21, 1999, Lecture Notes in Computer Science, vol. 1796, Springer-Verlag, pp. 153-171, 2000.
The first publicly disclosed authenticated-encryption scheme that achieves nearly the speed of a conventional, privacy-only encryption scheme, was developed by Charanjit Jutla, of IBM. Jutla describes two authenticated-encryption methods in his paper Encryption Modes with Almost Free Message Integrity, which first appeared in the Cryptology ePrint Archive on Aug. 1, 2000. (Later versions of this paper subsequently appeared in Advances in Cryptology—Eurocrypt 2001, Lecture Notes in Computer Science, vol. 2045, Springer-Verlag, May 2001, and as a submission to NIST (the National Institute of Standards and Technology), posted on NIST's website on Apr. 17, 2001.) One of Jutla's schemes is similar to CBC encryption and is called IACBC. The other one of Jutla's scheme is parallelizable mode that Jutla calls IAPM. Jutla's IACBC scheme is illustrated in FIG. 6, while his IAPM scheme is illustrated in FIG. 7.
Both IACBC and IAPM are authenticated-encryption schemes based on an n-bit block cipher, E. The modes require that the message M which is to be encrypted has a length which is a positive multiple of the block length n: say M=M[1] . . . M[m], where each M[i] is n bits long. The schemes employ two block-cipher keys, K1 and K2, which together comprise the encryption key K=(K1, K2). Conceptually, there are two processes involved: a “make-offset process” and a “main process”. The make-offset process is the same for IACBC and IAPM, while the main process in the two schemes differ.
Referring to the left hand side of FIGS. 6 and 7, the make-offset process in IACBC and IAPM uses the key K2 to map a random nonce, R, into a sequence of “pairwise independent” offsets, Z=Z[0], . . . , Z[m], Z[m+1]. Notice that one needs two more offsets than the message M is long (measured in blocks). Each offset is n bits. Jutla describes two different methods to realize the make-offset process. We shall describe these methods shortly; for now we view the production of offsets as a black-box process and we continue the explanation of the main-process of IACBC and IAPM.
The main process of IACBC is shown in the right-hand side of FIG. 6. Having used the key K2 and the nonce R to derive offsets Z[0], . . . , Z[m+1], encipher nonce R, now under key K1, to determine an initial chaining value, Y[0]=C[0]=EK1 (R). Then CBC encrypt M=M[1] . . . M[m]: for iε[1 . . . m], let Y[i]=EK1(Y[i−1]⊕M[i]). Next, mask each of these block-cipher outputs to determine a ciphertext block: for iε[1 . . . m], let C[i]=Y[i]⊕Z[i]. Call the string C=C[1] . . . C[m] is the “ciphertext core”. Next one computes a “checksum”, Checksum, by xoring the message blocks: Checksum=M[1]⊕ . . . ⊕M[m]. Next one forms an “authentication tag” by setting Tag=EK1(Checksum⊕Y[m])⊕Z[0]. The complete ciphertext specifies C[0], ciphertext core C=C[1] . . . C[m], and authentication tag Tag.
Decryption proceeds by the natural algorithm, as will be understood by those skilled in the art to which the present invention pertains, rejecting the ciphertext if the supplied authentication tag does not have the anticipated value.
We now describe the main process of IAPM, as show in the right-hand side of FIG. 7. Having used the key K2 and the nonce R to derive offsets Z[0], . . . , Z[m+1], encipher R, now using key K1, to determine an enciphered R-value, C[0]=EK1 (R). Now, for each iε[1 . . . m], message block M[i] is xored with offset Z[i], the result is enciphered using E (keyed by K1), and the resulting block is xored once again with offset Z[i], yielding a ciphertext block C[i]: that is, for each iε[1 . . . m], let C[i]=Z[i]⊕EK1(M[i]⊕Z[i]). Call C=C[1] . . . C[m] the ciphertext core. Next, compute a checksum, Checksum, by xoring together the message blocks: Checksum=M[1]⊕ . . . ⊕M[m]. Next, form an authentication tag, Tag, by xoring the checksum with offset Z[m+1], enciphering the result with EK1, and xoring the resulting block with offset Z[0]: Tag=Z[0]⊕EK1(Checksum⊕Z[m+1]). The complete ciphertext specifies C[0], ciphertext core C=C[1] . . . C[m], and authentication tag Tag.
Decryption proceeds by the natural algorithm, rejecting a ciphertext if its supplied authentication tag does not have the anticipated value. Namely, set R=EK1−1(C[0]) and use R and K2 to compute the offset sequence Z[0], . . . , Z[m+1]. Then compute the prospective plaintext M′=M[1] . . . M[m] by setting M[i]=Z[i]⊕EK1−1(C[i]⊕Z[i]). Next, re-compute the tag Tag′ that one would expect for the prospective plaintext M′: Checksum=M[1]⊕ . . . ⊕M[m] and Tag′=Z[0]⊕EK1(Checksum⊕Z[m+1]). If the expected tag, Tag′, matches the tag Tag appearing within the ciphertext, then the plaintext M is defined as the prospective plaintext M′. Otherwise, the received ciphertext is invalid.
It should be noted that IACBC is not parallelizable: one can not compute Y[i] until Y[i−1] has already been computed, making that method inherently sequential. But IAPM is fully parallelizable: all of the block-cipher calls needed to compute the ciphertext core can be computed at the same time.
We comment that the nonce R used in IACBC must be random. Use of a counter, or another adversarially predictable value, will result in an incorrect scheme.
It is important to optimize the speed of the make-offset process because, if it is slow, then the entire encryption process will be slow. Jutla's “method 1” for making offsets is depicted in FIG. 8. It works as follows. Let t be the number of bits needed to write m+2 in binary; that is,t=1+└ log2(m+2)┘.Now for each iε[1 . . . t], letIV[i]=EK2(R+i)where the indicated addition operation means computer addition of n-bit strings (that is, regard i as an n-bit string and add it to the n-bit string R, ignoring any carry that might be generated). The value R should be a random value (a counter, for example, will not work correctly). Offsets are now formed by xoring together different combinations of IV[i]-values. Jutla suggests the following to compute each Z[i] value, for iε[0 . . . m+1]. Number bit positions left-to-right by 1, . . . , t and let i1, . . . , itε[1 . . . t] denote all of the bit positions where i+1, when written as a t-bit binary number, has a 1-bit. Then setZ[i]=IV[i1]⊕ . . . ⊕IV[is]As an example, if m=3 then t=3 (since 5 is 101 in binary, which takes 3 bits to write down), Z[0]=IV[3] (since 1 is 001 in binary), Z[1]=IV[2] (since 2 is 010 in binary), Z[2]=IV[2]⊕IV[3] (since 3 is 011 in binary), Z[3]=IV[1] (since 4 is 100 in binary), and Z[4]=IV[1]⊕IV[3] (since 5 is 101 in binary).
We now describe Jutla's “method 2” for making offsets. Choose a large prime number p just less than 2n (e.g., choose the largest prime less than 2n) and then, for iε[0 . . . m+1], setZ[i]=(IV[1]+i·IV[2])mod p where IV[1]=EK2(R+1) and IV[2]=EK2(R+2) are defined as before. Again, nonce R should be a random value. The multiplication operator “·” refers to ordinary multiplication in the integers. Notice that for i≧1, the value of Z[i] can be computed from Z[i−1] by addition of IV[2], modulo p. This second method of Jutla's requires fewer block-cipher calls than the first method of Jutla's (block-cipher calls are used to make the IV[i] values, and now only two such values are needed, regardless of the length of the message). On the other hand, the mod p addition is likely more expensive than xor.
The property that Jutla demands of the sequence of offsets he calls pairwise independence, but Jutla does not use this term in accordance with its customary meaning in probability theory. Jutla appears to mean the property usually called strongly universal-2. A family of random variables Z[0], Z[1], Z[2], . . . , each with range D, is said to be strongly universal-2 if, for all i≠j, the random variable (Z[i], Z[j]) is uniformly distributed D×D.
Just subsequent to the appearance of Jutla's paper, two other authors, Virgil Gligor and Pompiliu Donescu, described another authenticated-encryption scheme. Their paper, dated Aug. 18, 2000 and entitled, http://www.eng.umd.edu/˜gligorFast Encryption and Authentication: XCBC encryption and XECB Authentication Modes, first appeared on Gligor's worldwide web homepage. The Gligor-Donescu authenticated-encryption scheme, which the authors call XCBC, resembles Jutla's IACBC. The scheme called XCBC$ is depicted in FIG. 9. The main difference between IACBC and XCBC$ is that the latter uses offsets Z[1], Z[2], . . . Z[m+1], which are now defined by: Z[0]=0 and, for iε[1 . . . m+1], Z[i+1]=Z[i−1]+R. The indicated addition means addition of binary strings, modulo 2n. Besides this “method 3” to create offsets, one should note that the value of Z[i] is now added (modulo 2n) to the block-cipher output, rather than being xored with the block-cipher output. Other differences between the Jutla and Gligor-Donescu schemes will be apparent to those skilled in the relevant art when comparing FIGS. 5 and 8.
As with Jutla's schemes, the nonce R in XCBC$ should be a random value; use of a counter, or another adversarially-predictable quantity, will not work correctly. The authors give a closely related scheme, XCBC, which employs a counter instead of a random value. That scheme is illustrated in FIG. 10. The complete ciphertext specifies the nonce, “ctr”, as well as C[1] . . . C[m]∥Tag.
It should be noted that XCBC and XCBC$, like IACBC, are sequential. Gligor's paper, as it originally appeared, did not suggest a parallelizable approach for authenticated encryption.
All of the available authenticated-encryption schemes we have described thus far share the following limitation: they assume that all messages to be encrypted have a length that is a positive multiple of the block length n. This restriction can be removed by first padding the message, using padding techniques well-known in the art. For example, one can append to every message M a “1” bit and then append the minimum number of 0-bits so that the padded message has a length which is a multiple of n. We call this “obligatory padding”. Decryption removes the obligatory padding to recover the original message. However, removing the length restriction in an authenticated-encryption scheme by obligatory padding is undesirable because it increases the length of the ciphertext (by an amount between 1 and n−1 bits). Furthermore, the method results in an extra block-cipher invocation when the message M is of a length already a positive multiple of n.
Another approach known in the art to deal with messages whose length is not a positive multiple of n is “ciphertext stealing CBC encryption”, which is like ordinary CBC encryption except that the final message block M[m] may have fewer than n bits and the final ciphertext block C[m] is defined not by C[m]=EK(M[m]⊕C[m−1]) but by C[m]=EK(C[m−1])⊕M[m]. One could hope to somehow use ciphertext stealing in an authenticated-encryption scheme, but it is not known how to do this in a way that does not destroy the authenticity property required of an authenticated-encryption scheme. In particular, natural attempts to try to modify IAPM in a manner that employs ciphertext stealing result in flawed schemes. A possible approach is to adapt ideas from the paper of Black and Rogaway, CBC MACs for Arbitrary-Length Messages: The Three Key Constructions, appearing in Advances in Cryptology—CRYPTO '00, Lecture Notes in Computer Science, Springer-Verlag, 2000. This paper teaches the use of obligatory padding for messages of length zero or a non-multiple of n, combined with no padding for messages of length of positive multiple of n, combined with xoring into the last block one of two different keys, as a way to differentiate these two different cases. However, such a method is tailored to the construction of message authentication codes, particularly message authentication codes based on the CBC MAC. It is unknown if such methods can be correctly adapted to an authenticated-encryption scheme like IAPM.
An additional limitation of the authenticated-encryption techniques we have discussed is the use of multiple keys. While well-known key-separation techniques can create as many “key variants” as one needs from a single underlying key, depending on such methods results in additional time for key-setup and additional space for key storage. It is unknown how one could devise a correct algorithm that would use only a single block-cipher key and use this one key to key all block-cipher invocations.
Method 1 for computing offsets is complex and slow, needing an unbounded number of block-cipher calls. The values IV[1], . . . , IV[t] can be computed during a pre-processing stage, but this pre-processing will be slow. Method 2 for computing offsets requires modulo p addition, which is not particularly fast because typical implementations use blocks having n=128 bits. Method 3 for computing offsets likewise requires addition (now modulo 2n) of quantities typically having n=128 bits, which may again be inconvenient because computers do not generally support such an operation, and high-level programming languages do not give access to the add-with-carry instruction that best helps to implement it. Most of the methods we have described require the use of a random nonce R, and the schemes will not work correctly should R be predictable by an adversary.